COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\\M0BASL30\M1BASI30\M2BASB30\.
C00046 00003	General Intelligence
C00056 ENDMK
C⊗;
\\M0BASL30;\M1BASI30;\M2BASB30;\.
\F0
\J	If you drive into the parking lot of the Stanford Artificial
Intelligence Laboratory, you will see a sign that says \F2CAUTION, ROBOT
VEHICLE\F0.  People react to this sign in various ways: some with hope,
some with fear, and some with curiousity and amusement.  What is there
to hope for or fear or be curious about?

	We can hope for a car that would drive itself to whatever
destination is keyed into its control unit.  Such a car could be used
by children, old people, and the handicapped.  It could
go by itself for servicing or to the store to pick up something that
had been ordered by telephone.  Naturally, it must drive more safely
than the best human drivers.  We can also hope that it would be able
to drive faster with safety and closer to other cars than can human drivers,
because it would react faster, would not suffer lapses of attention,
and would co-ordinate its movements with those of the other cars in
its vicinity.  Of course, robotics has many other possibilities besides
automated cars, but we will use it as an example for now.

	Artificial intelligence arouses a number of fears, but most of
them center on the idea that intelligent machines might prove
uncontrollable or than man might suffer irrepairable damage to his
pride and self respect.  For example, automated cars might crash when some
central computer broke down or they might take you somewhere you
didn't want to go.  Evil people might use intelligent machines to
conquer the world or the machines themselves might develop a desire
to conquer the world.  Even if nothing directly bad happened, people
might have lose their motivation to do anything once they knew that there were
machines smarter than they were.

	We will return to the hopes and fears later in the article,
when there is more information on which to base a discussion.
The curious also have lots of questions:

	1. How intelligent are the smartest present machines, and
what can they do?  How do they work?

	2. Is it possible for machines to be as intelligent or more
intelligent than people, and when might this come about, if at
all?

	3. What has been discovered about how to make machines
behave intelligently?

	4. What kind of personalities might intelligent machines
have?

	5. How soon can something practical come of it?

	The idea of intelligent machines originated in three stages:
The first stage was to make an artificial intelligent machine by
magic.  There is a Jewish legend of the Rabbi of Prague creating
a monster called the \F1Golem\F0 in the 16th century.  In the
early 19th century, Mary Wollstonecraft Shelley wrote about the creation
of Frankenstein's monster by science, but this science was just
a fictional device playing the same role as magic since how
the alleged science was supposed to work wasn't stated.  The idea
of a robot as a metal man built up from parts became common in
the 1920s.  However, serious efforts to understand what would
be required to make intelligent machines began only after the
design of the first universal computers in the late
1940s, almost all work since then has been based on them.

What is AI?

	\F1Artificial intelligence\F0 is the name given to the study
of the mechanisms of intelligence and how to make computers behave
intelligently.  Its ultimate scientific goal is a complete understanding
of the processes of solving intellectual problems.  Its ultimate
practical goal would be to make a computer program with all the
intellectual capabilities of a human and more, if possible.  If such
a computer with such a program were put into a suitable body and
provided with human-like goals, it would be the intelligent robot of
science fiction, but this would not necessarily be a good thing to do.

	Neither the theoretical goal of a fully understanding intelligence
nor the practical goal of a program with human level intelligence is
near or can be reached in one step.  It is not possible to estimate how
far off these goals are in time, because some conceptual breakthroughs
are almost certainly required, before we can estimate what programs will
have to be written.

	Progress is made in the theory of AI by identifying the mechanisms
of intelligence and studying their properties, and progress is made in
practice by making programs to carry out ever more difficult intellectual
tasks.  The theory and practice interact whenever we put intellectual
mechanisms we think we understand into a program and test whether the
program can do a certain task.  If it doesn't do the task well, we get
clues as to what mechanisms we don't yet understand.

	The study of intellectual mechanisms is related to other sciences.

	The psychologist is interested in the intellectual mechanisms of
the human and animal brain.  Whatever mechanisms they postulate to account
for the behavior of 
subjects, we can try to program if a mechanism has been precisely
described, and it can be tested whether the postulated mechanism is
adequate to produce the subjects' performance.
More directly, a computer scientist can make programs that attack problems
the way he thinks he does it himself.  This interaction with AI research
has caused psychologists to attribute to the human mind much more
complex intellectual structures than their methodology previously allowed
them to infer.  This is because there was just no way to produce human
problem solving ability in simple stimulus-response programs of the type
previously postulated.

	The neurophysiologist is interested in the structure and workings
of the brain starting with its basic element--the nerve cell.  At one time
it was thought that something could be learned about intelligent behavior
from studies of the nerve cell itself, but it was soon shown that any kind
of behavior could be built up from almost any possible model of the nerve
cell.  The physiologist's interaction with AI research as well as with psychology will
grow when they are in a position to observe the computational processes
carried out by large numbers of interacting nerve cells.

	Just as any computation can be carried out by nerve cells suitably
connected, so can any computation be carried out by vacuum tubes, by transistors,
or by integrated circuits.  Therefore, there is hardly any interaction
between AI and the subject of electronics.  Of course, advances in electronics
make computation cheaper and faster.

	AI also interacts with mathematical logic, philosophy and linguistics.
The languages of mathematical logic are used to express facts about the
world in some intelligent programs, and a new area in mathematical logic
is concerned with the properties of computer programs, which is also important for
AI.  The connection with philosophy comes about because a general
intelligent program must have built into it some view of what the world
is like in general, and philosophers have been studying this for 2000
years.  Both AI and linguistics are concerned with what sentences mean, and
translation from one language to another was one of the earliest AI tasks
attempted.


Computers

	The previous section referred to intelligent computer programs, and
you may have wondered whether perhaps the AI researchers were missing a bet
in confining their attention to computers.  Could it be that some other kind
of machine than a computer is required for intelligent behavior?  The answer
is no, but to see why, we have to know more about computers.

	By computer, we mean a stored program digital computer; this is the
dominant kind in use today.  Such a computer includes a main memory, an execution unit,
input-output units, and usually some secondary memory.

	The main memory stores information and gives it back on demand from
the execution unit.  Thus when the memory is given a \F1word\F0 of
information and an \F1address\F0, it writes the information in the
memory register having that address forgetting what was previously in that
register.  It will \F1read\F0 a word from a register when given the
address of the register and told to read.

	Any kind of information can be stored in a computer memory.  Indeed,
at one time the information may be a computer instruction and a millisecond
later, it may be a number or a few letters from someone's name or part
of a fact that tells what happens when an egg is dropped on a floor.
This is possible because any kind of information can be \F1encoded\F0 as
strings of 0's and 1's.  Thus the letter A is commonly represented as
1000001 and B as 1000010.  How many 0's and 1's a register can contain
depends on the computer.  A memory of 262,144 words with 36 \F1bits\F0
(0's or 1's) each, and where a word can be read or written in one
microsecond (millionth of a second) is commonly used for AI research.
The first draft of this article required 6800 computer words to store it.

	The execution unit takes words from memory and interprets them as
instructions and does what they tell it to do.  When it is ready to
begin obeying an instruction, it gets a memory address from a special
register called its \F1program counter\F0, gets the contents of
that address from memory and interprets it as an instruction.
There are several kinds of instructions: one may cause a number to be taken
from memory and added to a special register in the instruction unit,
another may cause the contents of such a register to be stored at a
specified address in memory, another may change the program counter
to a value that depends on whether the contents of a register is
positive or negative, and still others send information to the outside
world, say by sending a letter to a typewriter connected to the computer.

	What instructions there are depends on the computer, but the
instructions are always individually quite simple.  Complex behavior is
obtained by writing \F1programs\F0 containing hundreds or thousands
of instructions.  A typical program that plays chess moderately well
contains 12,000 instructions and uses another 4000 words of memory for
data, but programs of more than a million instructions have been written
by putting together subprograms written by many people.

	Systematic thought and experiment in artificial intelligence began
with the first computers in the late 1940s.  This is because stored
program digital computers are computationally universal, which means that
any computation doable by any machine can be done by a suitable program
on any stored program computer provided it has enough memory.  This fact
was proved for a particular kind of computer (never built) by the English
logician Alan Turing in 1936.  It means that the AI researcher doesn't have
to design and build a machine.  He doesn't have to know electronics and
most don't.  He has only to determine the procedure he wants the machine
to carry out and how to express it as a program in one of the languages
available on the computer he intends to use.  This is hard enough.

	Of course, it can happen that an important procedure in his
program can be done much faster on a special purpose machine than by a
program on a general purpose computer.  In this case, a special purpose
machine may be built and attached to the computer.  However, the research
had better be very sure that a procedure that is to be built into
hardware is just what he wants, since a machine is much harder to change
than a program.  Unfortunately, research in artificial intelligence has
not reached the point where just increasing the speed of computation
will allow large advances.


The experimental approach to AI

	The experimental approach to AI consists in taking a task, seeing
how far one can go in programming it by straightforward methods, and
trying to identify what intellectual mechanisms are involved.  Here are some
of the tasks that were attempted, something about the methods used, and
something about the results that were obtained.

	Making the computer play board games, especially chess, has been
a popular task.  Checkers, kalah, go, tictactoe (this is easy), and some
card games have also been attempted.  All the better chess programs built
so far work similarly.  A method is chosen for representing a chess position
in the memory of the computer using tables giving the location of each
piece and/or the occupant of each square.  A subprogram is written that
can list the legal moves in a position and the new position that results
from any move.

	With just this and another subprogram for recognizing checkmate
one could write a very simple program that would always determine the
best move.  It would simply test all sequences of moves of the two
players and work backwards from the end of the game.  The only trouble
with this simple program is that it wouldn't get done in the programmer's
lifetime because there are too many possibilities.  In fact, it wouldn't
get done before the stars cool off even if every atom in all the visible
galaxies of stars were a computer that could do an instruction in the time
it takes light to cross an atom---we call a calculation that wouldn't get
done under those conditions \F1strongly impractical\F0.  Therefore it is
necessary to use some tricks, called \F1heuristics\F0, for avoiding this
\F1combinatorial explosion\F0.

	The heuristics used involved looking at only some of the possible
continuations from the position in which the machine has to find a move.
The \F1look-ahead\F0 is stopped at some point and an approximate rule is
used to evaluate the position.  Thus the program looks at only part of the
so-called \F1move tree\F0.  (A branching diagram like that of figure 1
giving the moves and their successors is called a move tree.)  The quality
of the program and how fast it plays are determined by what moves are
examined and how the ultimate positions are evaluated.  This evaluation
usually takes into account the number of pieces of each kind posessed
by each player, some measure of control of important squares like those
in the center of the board and those near the kings, and other aspects
of the postion considered important by chess players.  The "how to do it"
books by famouts chess players are quite useful in making up the
evaluation rules.
However, it is has turned out that the rules that determine what moves
the program will consider are more important than the evaluation rules.
Thus, when the program makes a wrong move, it is more often because it
wasted its time looking at silly moves and missed looking at an important
move, rather than because it misevaluated a position.

	Here are two heuristics used in recent chess programs but which
are applicable to other games as well.  Neither was used in the earliest
chess programs even though they are essential for good play and humans
clearly use them.  Therefore, not using them was a failure in self-observation
by excellent chess players.  There are doubtless many more failures of
self-observation on the part of people trying to program computers to
solve problems the way they themselves do it.  The fact that famous
chess players have so far not been very successful in their chess programs
indicates this.

	The first heuristic is called the \F1alpha-beta heuristic\F0 for
irrelevant reasons and is illustrated by figure 2.  If the program looks at
the top three end positions and determines that the values of these
positions for the second player are 8, 1 and 6, it will conclude
that if the first player moves to the postion labelled A, the second
player can reach a position worth an estimated 8 points and can't do
better.  If the program now considers a move to B for the first
player and looks at the end position labelled 9 and having 9 as a value,
it need not look at the positions labelled  X and Y, because it doesn't
matter what their values are.  Think about why.

	Not using the alpha-beta heuristic in its general form is
disastrous; it can mean looking at a million positions to get information
that can be obtained by looking at a thousand.

	The \F1killer heuristic\F0 says that if a certain move for one
side has turned out well in the analysis of one postion, it should be
considered promptly in the analysis of other positions.  Humans all use
it, but not all programs written do it.

	Chess programs of this general type have obtained tournament ratings
of about 1750 in competition with human players - the master level starts
at 2200, and these programs have not improved much in the last few years.
They play particularly badly if the opponent survives until the end game,
because good end game play depends on intellectual mechanisms not yet
incorporated in programs.  My guess is that the next big improvement in
chess programs will come from a good scheme for recognizing that parts
of a position belong to general patterns an searching for moves relevant to
these patterns.

	AI researchers have been criticized for studying chess.  "Why don't
you work on important problems requiring intelligence like government policy?"
we have been asked.
This is like asking a geneticist why he studies fruit flies
when elephants are more important.  You can't keep a thousand elephants in
a bottle on a laboratory shelf, and you can't get a new generation of
offspring in a few days.  Chess has the advantage for AI research that it
is easy to compare the performance of the programs with human performance.
Unfortunately, some of the chess programmers are sportsmen and not scientists;
they compete with each other but don't write papers describing how they
do it.

	The best chess program in 1974 is probably Chess 4.0 written by
David Slate and is colleagues at Northwestern University and using the
Control Data 6600 computer.

	In one non-trivial game, kalah, a program (for a machine that
no longer exists) beat the best human players.  In checkers, the best
program plays at master level.  In the oriental game of \F1go\F0, the
best program can't beat the rankest beginner.  The difference is much more
a matter of the intellectual mechanisms required for good play rather
than of the effort that has been put in.  \F1Go\F0 requres the recognition
and separate evaluation of subpositions rather than working with the list
of all legal moves.

	Many programs have been written to prove mathematical theorems.
Herbert Gelernter of I.B.M., using an idea of Marvin Minsky of M.I.T.,
wrote a program that proves theorems in high school plane geometry.
It used a kind of diagram in the memory of the computer consisting of the
co-ordinates of a set of points satisfying the hypotheses of the theorem.
Thus if it was asked to prove two line-segments equal, it would try to
find two triangles it could prove congruent of which the line-segments were
corresponding sides.  But before trying to prove the triangles congruent,
it would check congruence numerically in the diagram.  The program did
better than high school students in a limited part of plane geometry
(no circles and no constructions), but no attempt was made to extend its
metheod to other domains.

	Most of the work in computer theorem proving has been based on
a scheme called resolution invented by J. Alan Robinson for proving
theorems in a branch of mathematical logic called predicate calculus.
This scheme can't be explained here, but the general idea is to
combine the negation of the proposition to be proved with the initial
assumptions to get new statements and to repeat the process with
these new statements until a contradiction has been reached.  This
shows that the negation of the goal is false and hence the goal
statement is true.  Many heuristics have been programmed in order to
reduce the combinatorial explosion, but it is still quite impractical
for important mathematical theorems.  Compared to human mathematicians,
the results are laughable except in a few special areas of mathematics
where human intuition isn't much good.  A few results were obtained
by a program of David Luckham's before they were obtained by hand.

	The main limitation on the present resolution programs is that there
is no good way of introducing heuristics that depend on the subject domain.
There isn't a good way of using examples, and not enough ways are known
for preventing the program from generating large numbers of trivial
conclusions.  Theorem proving is not merely important as an example,
because many other important problems can be put into the form of
proving theorems in logic.

	Natural languages, e.g. English, have been the subject of programs
to translate from one language into another, to answer
questions in English about a body of data stored in the computer,
to simulate the belief system of a paranoid, and to manipulate blocks
in accordance with English language commands.  The earliest translation
programs tried to go from a sentence in one language to a sentence in
another purely on the basis of a dictionary and the grammatical structure
of the sentences, i.e. without the program having to deal with
the meaning of the sentence.  This worked often enough to be intitially
encouraging, but it eventually became clear that good translatin requires
some measure of understanding.  A famous example, whose authenticity I
don't guarantee, is translating "The spirit is willing, but the flesh is
weak" into Russian and back and coming out with "The vodka is strong,
but the meat is rotten".

	A recent program that showed the advantage of "understanding"
a limited number of words in a limited domain is the \F1Blocks\F0
program of Terry Winograd.  Imagine a table covered with blocks of
various shapes and colors and an arm that can move them around.  The
program can obey commands and answer questions like

	1. Will you please stack up both of the red blocks and either
a green cube or a pyramid? OK.

	2. Which cube is sitting on the table?  The large green one
which supports the red pyramid.

	3. Is there a large block behind a pyramid?  Yes, three of them:
a large red one, a large green cube, and the blue one.

	In order to obey these commands and answer the questions, it had
to use information about blocks in general and about the particular
configuration of the blocks on the table.  Such information is often
required in order merely to connect pronouns and nouns.

	Besides these purely intellectual tasks, AI research has
tried to duplicate sensory and motor activities of the human including
vision, speech, and assembling things out of parts and driving a vehicle
so as to get somewhere avoiding obstacles.

	The earliest vision work concerned the classification of scenes
into categories,\F1e.g.\F0 pictures of letters of the alphabet were
identified.  These systems used collections of features of the pictures and
were \F1trained\F0 to make the classification by presenting sample
pictures and telling the program which classification each sample
belonged to.  If the classification depends on the presence of the
features in a simple enough way, the program can learn from the training
sequence how to classify new pictures correctly.  This work lent itself
to mathematical study more than other AI problems.

	A different approach is required when the vision is in support
of manipulation.  If an arm is to pick up a block, it is not enough to
be able to classify pictures according to whether a block is present.
The program must find a block amidst other objects and must determine
its location and orientation so that other programs can decide where
to reach and with what orientation of the hand.  Present programs work
pretty well for scenes made up of objects with flat faces, but a bare
start has been made on natural scenes that contain curved and irregular
objects.


Theory

	The efforts to make computer programs for increasingly difficult
tasks helps identify intellectual mechanisms that are applicable to
many tasks.  The theoretical study of these mechanisms should in turn
help the programmers.  Already it seems that the mechanisms used depend
more on the kind of task than on the performer.  Thus we would expect that
men, machines, and Martians must all include tree search with the alpha-beta
heuristic in their respective ways of playing chess if they are to play well.

	Here are some of the intellectual mechanisms that have been studied:

	1. \F1Tree search\F0 is examining possible actions, the possible
events that may result from these actions, and the further actions that
then become possible, etc.  Tree search comes up in game playing,
theorem proving, common sense reasoning, and many other tasks.  Research
has concentrated on reducing the amount of search that has to be done.

	2. \F1Hill climbing\F0 involves seeking a goal by being able to compare two 
possible situations in order to determine which is better.  Hill climbing is very efficient compared to 
tree search for the goal when it is possible.  The problem is to get a good way
of comparing situations.

	3. \F1Isolation and combination\F0  Humans solve problems by identifying 
subproblems that can be solved separately.  While there are some examples of this
in AI, there are no general methods as yet.

	4.\F1Pattern recognition.\F0  Often opportunities for successful action
depend on recognizing that a part of the information at the program's disposal is 
an example of a particular pattern.  Pattern recognition is well developed in 
natural language studies, but there are unexploited possibilities in vision, in 
games, and in common sense reasoning.  More general notions of pattern are needed.

	5. It is usually much more difficult to modify the behavior of a present day computer program than 
to teach a person a new trick.  A chess player can be told about "smothered mates"
and will use the information without the teller having to know much about the 
person being told except that he knows English and something about chess.  To 
modify a program to take smother mates into account usually requires a detailed
understanding of the program and modifications in several places.  It is as if human
education were done by brain surgeons reconnecting nerve cells in new arrangements.

	Improved modifiability is especially important when we want the program to 
\F1learn, i.e.\F0 to modify itself.  Programs can be made to learn from experience when the aspects of behavior to be
modified are isolated.  It has been expecially easy to make programs that learn the best value of a 
number.  For example, a chess program could easily be made to learn how many pawns a 
queen is worth.  In general, a program can learn for itself only what it could be told.

	Three approaches to the modifiability problem are worth mentioning.  First, better 
programming languages that allow easy description of patterns help express separate aspects of 
the desired behavior in separate and readily modified ways.  Second, new style
\F1automatic programming\F0 gets the computer to go from facts to efficient programs
using these facts.  Third, we are gradually learning to make computers reason, 
\F1i.e.\F0 draw conclusions from information represented in declarative sentences.

	It is generally agreed that progress in the representation of information about the world is most 
needed in AI in the next few years.\.
General Intelligence

	\JA program that plays good chess needs intellectual mechanisms that are 
also used in other intellectual activities.  Nevertheless, the program can't do 
anything but play chess and doesn't satisfy our intuition that a \F1truly\F0
intelligent program wouldn't have chess built in but would learn it as a human
does and would adapt its general intelligence to choose and solve particular
problems.  There is no such generally intelligent program today.

	Such a program has to be general in two ways--in what it knows and in its
ability to use knowledge to solve problems.

	Here are some things a general intelligence must know:

	1.  It must know about events happening in time.

	2.  It must know how its own actions and those of people affect events.

	3.  It must be able to compare situations and decide whether it likes one
better than another.

	4.  It must know about material objects, their locations in space, their motions,
and how they are built up from smaller objects and can be destroyed.

	5.  For many purposes, it must understand itself as a material object and
how it is affected by its own actions and other events and how its physical state affects
its possibilities for action.

	6.  It must know about knowledge and how it can be obtained, \F1e.g.\F0 by
observation, by asking other people (thus it has to know that information operators
know telephone numbers) and by reading.

	Besides this, it has to know lots of particular facts relevant to solving
particular problems such as the moves of the chess men and what happens to eggs 
dropped on the floor.

	This is only a sample of what a general intelligence must know, because 
no one has been able to write down a complete list--more from confusion than 
from lack of diligence.  We do not know what a general intelligence has to know.

	In this puzzlement artificial intelligence researchers are not alone, because 
for more than two thousand years, philosophers have been concerned with the general
structure of the world and the nature of knowledge.  Unfortunately, they don't
seem to have come up with anything concrete enough to be the basis of a computer
program.  Indeed, in the 1930's, some philosophers became so discouraged with the
problem that they denied that there was anything to know about the structure of the world
apart from the particular sciences.  There is some hope that artificial intelligence
research can help with the philosophical problems, because instead of beginning by
worrying about knowledge in general, we can start by trying to put enough knowledge 
about knowledge into a computer program so that it can ask Bill who might know
Christine's telephone number.

	There is controversy about how to represent knowledge in the memory of the
computer.  Some think most knowledge should be represented by procedures that tell
what will happen when certain actions are performed.  Special computer languages called
PLANNER and CONNIVER have been invented for this purpose.  Others emphasize representing
knowledge by declarative sentences.  This group is divided between those who use a mathematical 
language called predicate calculus and those  whose approach is based
on  a natural language like  English.  The former  have the advantage
that it is definite in mathematical logic when one  statement follows
from  another, and  the  latter have  the  advantage that  presumably
everything that has to be said, can be said in English.

	Besides general information and general ways of representing special information,
a general intelligence also needs general methods of problem solving and general ways of representing
special methods of problem solving.

Social Consequences

	Some research  in  AI has  already had  application in  other
fields.  This includes the identification of chemical structures that
result in a given mass spectrogram, some of the vision work,  and the
work on programming language.  More appplications are expected in the moderately new future 
to such fields as automatically driving a vehicle and automatically assembling machines from 
parts.  Socially, these applications will be similar to other advances in technology--
greater prosperity and individual choice accompanied by some problems of adjustment
that depend on the particular case.

	However, a complete solution of the AI problem, \F1i.e.\F0 programs as smart as people would
be something quite different.  Here are some observations:

	1.  If we can make machines as intelligent as people, we can make them much
smarter just by increasing their speed and memory size.  Thus the science fiction idea of robots as 
another race of humans is unrealistic.

	2.  Humans have complicated motivational and emotional structures that arose
in the course of our evolution from lower animals.  In particular, we change our goals often,
and we have a sense of our own rights and self esteem.  It would not seem advantageous to put artificial intelligence
in human-like bodies and try to give them human motivations.  It would seem better to 
let them inhabit computers and answer our questions as best they can.

	3.  If we had a very intelligent program. one of the first problems to put it on is
determining the consequences of the various policies that might be adopted concerning its use.

	4.  The most likely choice to me is to use artificial intelligence to enhance
human intelligence and individuality, perhaps even by some man-machine merger as depcted in
some science fiction stories.

	5.  All this is very much like concocting a recipe for rabbit stew without knowing
how to catch rabbits.  We will have to know a lot more about artificial
intelligence before we can face decisions about how to use it.\.